1. Field of the Invention
The present invention generally relates to general purpose digital data processing systems and more particularly relates to such systems which perform scaling, dithering, and/or data remapping operations on a stream of image data.
2. Description of the Prior Art
Digital imaging has become increasingly popular over the past several years. Many types of documents that were in the past stored as paper documents may now be stored as digitized images. Examples of typical documents that are currently stored as digital images including engineering drawings, art work, and various other non-textual documents.
Scanners and video cameras may digitize documents thereby coding them as ones and zeros. In a typical system, a one represents a white portion of a document and a zero represent a black portion of a document. Digitizing devices may view a document as a large number of pixels wherein each pixel has a degree of darkness. The degree of darkness of a particular pixel may fall on a light to dark continuum. The digitizing device may assign the particular pixel a value of zero if the degree of darkness does not exceed a predetermined threshold of darkness. Similarly, the digitizing device may assign the particular pixel a value of one if the degree of darkness does exceed the predetermined threshold of darkness. The predetermined threshold of darkness can often be adjusted by the user of the digitizing device. In this way, a paper document may be represented as an array of pixels where each pixel may be represented by a one or a zero. A computer may be used to manipulate, store, or transmit the pixels as desired.
Often a document may have shades of gray contained therein rather than be made up of strictly black and white pixels. For these documents, a number of digital bits may be used to describe a particular shade of gray of a corresponding pixel within the digitized image. Depending on the number of shades of gray utilized, the quality of the duplicate image may be increased. For example, if an image utilizes four shades of gray to describe the original image, two bits of digital data may be used to describe each pixel within the image. Each combination of the two digitized bits describes one of the four shades of gray. Similarly, if an image utilizes 256 shades of gray, eight bits of digital data may be used to describe each pixel within the image. For high quality digitized images, it is common to use eight bits of digital data to describe each pixel within the image thereby allowing each pixel to be stored as one of 256 shades of gray.
The number of bits or pixels in an image depends on the size of the image and on the resolution of the digitizing device. Resolution is a measure of the precision of the digitizing device and is typically expressed in Dots Per Inch (DPI). The greater the DPI of a digitizing device, the more likely the digitized image will appear similar to the original document when a computer displays or prints the digitized image. Common resolutions used today include 100, 150, 200, 240, and 300 DPI.
A problem that is frequently encountered when various shades of gray are used when digitizing an image is that many output devices are limited to black and white pixels. Typical output devices include printers and CRT screens. This problem may be minimized by using a technique know as dithering. Dithering is the process of translating image data that contains data bits which indicate the grayness of a pixel into a digital image that is strictly represented by black and white pixels. There are several dithering algorithms that are widely used today.
One dithering algorithm that is popular allocates a number of printer "dots" to each pixel of the digitized image. It was recognized that it is possible to represent various shades of gray by having a number of dots of a printer correspond to each pixel in the image. By increasing the number of dots that are coded black within the corresponding pixel, the shade of gray appearing to the naked eye may be darkened. If the number of "dots" that are allocated to each pixel of the digitized image are increased, more shades of gray may be represented on the resulting printer or CRT screen. As long as the printed document is kept a reasonable distance from the eye, the image appears analog rather than digital.
Another dithering algorithm used today only requires one "dot" of a printer to be allocated to each pixel of the digitized image. In this algorithm, a predetermined number of pixels located in the same proximity to a selected pixel may be used to calculate whether the selected pixel should be black or white. Typically, the predetermined number of pixels located in the same proximity to the selected pixel are interpolated or averaged with the selected pixel to determine whether the selected pixel should be black or white. While this algorithm generally does not produce the same quality of image as the previously described dithering algorithm, much larger images may be printed because of the one-to-one correspondence between the image pixels and the printer "dots".
A dithering scheme which combines the above described dithering algorithm with a simple scanning algorithm is described in U.S. Pat. No. 5,307,426, issued on Apr. 26, 1994 to Kanno et al. Kanno employs a dithering scheme for images which contain a character region and a photographic region. For the character regions of an image, Kanno may store the quantized pixels as a one or a zero thereby allowing a high resolution of pixels in that region. For the photographic regions of an image, Kanno may store the quantized pixels as a number of data bits indicating the grayness of the corresponding pixel. This scheme exploits the fact that the maximum density difference of pixels in a character region of an image is typically large and the maximum density difference of pixels in a photographic region of an image is typically small. Kanno employs a quantization error technique to determine which regions within an image are character regions and which are photographic regions.
Because digitized images have become so popular in recent years, computer designers have developed many methods of manipulating the digitized image data for various purposes. The dithering methods described above are exemplary of some of these data manipulation methods.
Another example of a data manipulation method is know as scaling. Scaling refers to changing the size or other characteristic of an image in a predetermined way. For example, a digitized image may be "reduced" or "enlarged" by a predetermined factor. When scaling the size of a digitized image, the algorithm typically takes "M" data units as input and produces "N" data units as an output, where "M" is different than "N". A concrete example of this is when a life size image is captured at one resolution and displayed on a monitor having another resolution. In this situation, the digitized image must be scaled. Another example includes the scaling of the "grayness" of an image, either lighter or darker.
Yet another example of a data manipulation method is termed remapping. Remapping refers to performing an arbitrary function Y=F(X) on an input data stream to produce a different output data stream. One application for remapping may be to accent or highlight certain areas of an image.
Similar to the remapping manipulation method is the Nth order FIR filter manipulation method. The Nth order FIR filter manipulation method is a function which takes an input data element `X1` as well as "N" of the previous data elements and computes the output according to the equation y=K1*X1+K2*X2+. . . +KN*XN, where K1 . . . KN are arbitrary numbers used to weight the input values. K1 . . . KN are not necessarily constant values and therefore the relative weights may change with time. The Nth order FIR filter manipulation method may be used to "filter" predetermined characteristics from a digitized image. Digital signal processing techniques may also be employed to exploit this manipulation method.
In a typical prior art high speed systems, separate dedicated circuitry is provided for each of the manipulation methods described above. Therefore, if a prior art system is capable of performing a scaling, dithering, and remapping function, three different sets of hardware are typically incorporated into the system. A problem with the prior art systems is that typically only one of the manipulation algorithms is functioning at any given time. That is, the user of the computer system typically sets the system into a given data manipulation mode and all image data processed thereafter is processed in accordance with the preset manipulation mode. At a later time, the user may set the system into another manipulation mode wherein all image data processed thereafter is processed in accordance to the newly set manipulation mode. Since separate hardware is typically provided for each manipulation mode, the hardware not associated with the enabled manipulation mode is unused. This may consume unnecessary size and power within the computer system.